package org.example.top40;


import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    //双向链表
    private class DListNode{
        int key;
        int value;
        DListNode pre;
        DListNode next;

        public DListNode() {
        }

        public DListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //初始化LRU
    Map<Integer,DListNode> map=new HashMap<>();
    int size;
    int capacity;
    DListNode head,tail;
    public LRUCache(int capacity){
        this.capacity=capacity;
        this.size=0;
        head=new DListNode();
        tail=new DListNode();
        head.next=tail;
        tail.pre=head;
    }
    public int get(int key){
        DListNode node = map.get(key);
        if(node==null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    public void put(int key,int value){
        DListNode node = map.get(key);
        if(node==null){
            DListNode newNode = new DListNode(key, value);
            map.put(key,newNode);
            addToHead(newNode);
            size++;
            if(size>capacity){
                DListNode last= removeLast();
                map.remove(last.key);
                size--;
            }
        }else{
            node.value=value;
            moveToHead(node);
        }
    }
    private void addToHead(DListNode node) {
        node.pre=head;
        node.next=head.next;
        head.next.pre=node;
        head.next=node;
    }
    private void removeNode(DListNode node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }
    private void moveToHead(DListNode node) {
        removeLast();
        addToHead(node);
    }
    private DListNode removeLast() {
        DListNode last=tail.pre;
        removeNode(last);
        return  last;
    }
}
